#include <iostream>
#include <vector>
using namespace std;

class BinarySearch {
public:
  /**
   * @brief 折半查找：查找是否存在值为 key
   * 的数，如果存在则返回目标元素的下标索引，否则返回 -1
   *
   * @param a 查找数组
   * @param len 查找数组长度
   * @return int 返回的下标索引
   */
  static int binarySearch(int a[], int len, int key) {
    int left = 0, right = len - 1, mid;
    while (left <= right) {
      mid = left + ((right - left) >> 1);
      if (a[mid] > key)
        right = mid - 1;
      else if (a[mid] < key)
        left = mid + 1;
      else
        return mid;
    }
    return -1;
  }
  /**
   * @brief 查找算法的递归写法
   *
   * @param a 查找表
   * @param left 查找表的左边界
   * @param right 查找表的右边界
   * @param key 目标值
   * @return int 返回值为 key 的索引，如果未找到则直接返回 -1
   */
  static int recursiveBinarySearch(int a[], int left, int right, int key) {
    // 边界条件
    if (left > right)
      return -1;
    int mid = left + ((right - left) >> 1);
    if (a[mid] > key)
      return recursiveBinarySearch(a, left, mid - 1, key);
    else if (a[mid] < key)
      return recursiveBinarySearch(a, mid + 1, right, key);
    return mid;
  }

  /**
   * @brief 查找表中比 target 大的第一个元素
   *
   * @param a 待查找表
   * @param len 待查找表的长度
   * @param target 目标值
   * @return int 返回目标值的索引，如果表中所有元素都比 target 大，则返回
   * -1，如果表中所有元素都比 target 小则返回 len
   */
  static int greaterBinarySearch(int a[], int len, int target) {
    int left = -1, right = len, mid;
    while (left + 1 != right) {
      mid = left + ((right - left) >> 1);
      if (a[mid] <= target)
        left = mid;
      else
        right = mid;
    }
    return right;
  }

  /**
   * @brief 查找算法：找到第一个大于或等于目标值的元素所在索引位置
   *
   *
   * @param a 待查找表
   * @param len 待查找表的长度
   * @param target 目标值
   * @return int 返回目标值的索引，如果表中所有元素都比 target 大，则返回
   * -1，如果表中所有元素都比 target 小则返回 len
   */
  static int greaterEqualBinarySearch(int a[], int len, int target) {
    int left = -1, right = len, mid;
    while (left + 1 != right) {
      mid = left + ((right - left) >> 1);
      if (a[mid] < target)
        left = mid;
      else
        right = mid;
    }
    return right;
  }
};

int main() {

  int a[12] = {1, 2, 3, 4, 4, 4, 4, 4, 4, 11, 11, 11};
  int index = BinarySearch::greaterEqualBinarySearch(a, 12, 4);
  cout << index;
  return 0;
}